package com.tree.stack;

import com.alibaba.fastjson.JSON;

import java.util.Stack;

/**
 * package com.tree.stack
 * description:
 *
 *  要求：
 *      将栈从大到小的顺序排序，只允许申请一个栈。除此之外， 可以申请1个变量，不能申请其他数据结构，如何完成排序
 *  思路：
 *      排序栈为stack，申请栈为help, 取顶部元素值为top， stack上执行pop的值为current
 *      取top 与help整个栈对比{
 *          1. 如果current <= top, 入help栈
 *          2. 否则current 出栈，入stack栈
 *      }
 *
 * @author tree
 * @date 2019-10-11 11:14
 */
public class StackSort {
    private static Stack<Integer> stack = new Stack<Integer>();
    private static Stack<Integer> help = new Stack<Integer>();

    public static void main(String[] args) {
        stack = StackUtil.getStack(true);
        System.out.println(JSON.toJSONString(stack));

        //取左边的值， 与右边的所有值从顶到底比较，直到第一个左边的值>右边的值
        while (!stack.isEmpty()){
            int current = stack.pop();
            //如果左边的比右边的大，则把右边的值压入左边，直到右边的值小于等于左边
            while( !help.isEmpty() && current > help.peek()){
                    stack.push(help.pop());
                }
            help.push(current);
        }

        System.out.println("stack="+JSON.toJSONString(stack));
        System.out.println("help="+JSON.toJSONString(help));

    }
}
